package 递归.快排;

import java.util.Random;

/*三路快速排序*/
public class QuickSort {
    private QuickSort(){};
    public static  void sort(int []arr){
        Random random = new Random();
        sort(arr, 0, arr.length-1, random);
    }
    public static void sort(int []arr, int l, int r, Random random){
        if (l >= r){
            return;
        }
        int p = l + (random.nextInt(r-l+1));

        swap(arr, p, l);
        /*
         * 标定值， 小于区域，等于区域， 大于区域
         * arr[l+1, lt].arr[lt+1, i-1]..arr[gt, r]*/
        int i = l+1;
        int lt = l;
        int gt = r+1;
        while (i < gt){
            if (arr[i] < arr[l]){
                lt++;
                swap(arr, i, lt);
                i++;
            }else if (arr[i] > arr[l]){
                gt--;
                swap(arr, gt, i);
            }else {
                i++;
            }
        }
        swap(arr, l, lt);
        /*
         * 标定值， 小于区域，等于区域， 大于区域
         * arr[l, lt-1].arr[lt, gt-1]..arr[gt, r]*/
        sort(arr, l, lt-1, random);
        sort(arr, gt, r, random);
    }
    /*找到标定值的位置分割*/
    /*原地排序*/
    public static void swap(int []arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        int[] a = {8,4,3,5,7,6};
        QuickSort.sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }
}
